Product Code Database
In computer science, tree traversal (also known as tree search and walking the tree) is a form of graph traversal and refers to the process of visiting (e.g. retrieving, updating, or deleting) each node in a tree data structure, exactly once. Such traversals are classified by the order in which the nodes are visited. The following algorithms are described for a binary tree, but they may be generalized to other trees as well.
Depth-first search is easily implemented via a stack, including recursively (via the call stack), while breadth-first search is easily implemented via a queue, including corecursively.
To traverse binary trees with depth-first search, perform the following operations at each node: Binary Tree Traversal Methods
The trace of a traversal is called a sequentialisation of the tree. The traversal trace is a list of each visited node. No one sequentialisation according to pre-, in- or post-order describes the underlying tree uniquely. Given a tree with distinct elements, either pre-order or post-order paired with in-order is sufficient to describe the tree uniquely. However, pre-order with post-order leaves some ambiguity in the tree structure.
There are three methods at which position of the traversal relative to the node (in the figure: red, green, or blue) the visit of the node shall take place. The choice of exactly one color determines exactly one visit of a node as described below. Visit at all three colors results in a threefold visit of the same node yielding the “all-order” sequentialisation:
The pre-order traversal is a topologically sorted one, because a parent node is processed before any of its child nodes is done.
Post-order traversal can be useful to get postfix expression of a binary expression tree.
In a binary search tree ordered such that in each node the key is greater than all keys in its left subtree and less than all keys in its right subtree, in-order traversal retrieves the keys in ascending sorted order.
In a binary search tree ordered such that in each node the key is greater than all keys in its left subtree and less than all keys in its right subtree, reverse in-order traversal retrieves the keys in descending sorted order.
Depending on the problem at hand, pre-order, post-order, and especially one of the number of subtrees − 1 in-order operations may be optional. Also, in practice more than one of pre-order, post-order, and in-order operations may be required. For example, when inserting into a ternary tree, a pre-order operation is performed by comparing items. A post-order operation may be needed afterwards to re-balance the tree.
Post-order traversal can generate a postfix representation (Reverse Polish notation) of a binary tree. Traversing the depicted arithmetic expression in post-order yields " A B C − * D E + +"; the latter can easily be transformed into machine code to evaluate the expression by a stack machine. Post-order traversal is also used to delete the tree. Each node is freed after freeing its children.
In-order traversal is very commonly used on binary search trees because it returns values from the underlying set in order, according to the comparator that set up the binary search tree.
Implementations in iterative approach are able to avoid the drawbacks of recursion, particularly limitations of stack space and performance issues.
Several alternative implementations are also mentioned.
'''procedure''' preorder(node)
'''if''' node = '''null'''
'''return'''
visit(node)
preorder(node.left)
preorder(node.right)
| '''procedure''' iterativePreorder(node)
'''if''' node = '''null'''
'''return'''
stack ← '''empty stack'''
stack.push(node)
'''while''' '''not''' stack.isEmpty()
node ← stack.pop()
visit(node)
// right child is pushed first so that left is processed first
'''if''' node.right ≠ '''null'''
stack.push(node.right)
'''if''' node.left ≠ '''null'''
stack.push(node.left)
|
'''procedure''' postorder(node)
'''if''' node = '''null'''
'''return'''
postorder(node.left)
postorder(node.right)
visit(node)
| '''procedure''' iterativePostorder(node)
'''if''' node = '''null'''
'''return'''
stack ← '''empty stack'''
lastNodeVisited ← '''null'''
'''while''' '''not''' stack.isEmpty() '''or''' node ≠ '''null'''
'''if''' node ≠ '''null'''
stack.push(node)
node ← node.left
'''else'''
peekNode ← stack.peek()
// if right child exists and traversing node
// from left child, then move right
'''if''' peekNode.right ≠ '''null''' '''and''' lastNodeVisited ≠ peekNode.right
node ← peekNode.right
'''else'''
visit(peekNode)
lastNodeVisited ← stack.pop()
|
'''procedure''' inorder(node)
'''if''' node = '''null'''
'''return'''
inorder(node.left)
visit(node)
inorder(node.right)
| '''procedure''' iterativeInorder(node)
'''if''' node = '''null'''
'''return'''
stack ← '''empty stack'''
'''while''' '''not''' stack.isEmpty() '''or''' node ≠ '''null'''
'''if''' node ≠ '''null'''
stack.push(node)
node ← node.left
'''else'''
node ← stack.pop()
visit(node)
node ← node.right
|
'''procedure''' bubbleUp(array, i, leaf)
k ← 1
i ← (i - 1)/2
'''while''' (leaf + 1) % (k * 2) ≠ k
i ← (i - 1)/2
k ← 2 * k
'''return''' i
'''procedure''' preorder(array)
i ← 0
'''while''' i ≠ array.size
visit(array[i])
'''if''' i = size - 1
i ← size
'''else if''' i < size/2
i ← i * 2 + 1
'''else'''
leaf ← i - size/2
parent ← bubble_up(array, i, leaf)
i ← parent * 2 + 2
'''procedure''' search(bst, key)
// returns a (node, stack)
node ← bst.root
stack ← '''empty stack'''
'''while''' node ≠ '''null'''
stack.push(node)
'''if''' key = node.key
'''return''' (node, stack)
'''if''' key < node.key
node ← node.left
'''else'''
node ← node.right
'''return''' ('''null''', '''empty stack''')
The function inorderNext returns an in-order-neighbor of node, either the (for dir=1) or the (for dir=0), and the updated stack, so that the binary search tree may be sequentially in-order-traversed and searched in the given direction dir further on.
'''procedure''' inorderNext(node, dir, stack)
newnode ← node.child[dir]
'''if''' newnode ≠ '''null'''
'''do'''
node ← newnode
stack.push(node)
newnode ← node.child[1-dir]
'''until''' newnode = '''null'''
'''return''' (node, stack)
// node does not have a dir-child:
'''do'''
'''if''' stack.isEmpty()
'''return''' ('''null''', '''empty stack''')
oldnode ← node
node ← stack.pop() // parent of oldnode
'''until''' oldnode ≠ node.child[dir]
// now oldnode = node.child[1-dir],
// i.e. node = ancestor (and predecessor/successor) of original node
'''return''' (node, stack)
Note that the function does not use keys, which means that the sequential structure is completely recorded by the binary search tree’s edges. For traversals without change of direction, the (amortised) average complexity is because a full traversal takes steps for a BST of size 1 step for edge up and 1 for edge down. The worst-case complexity is with as the height of the tree.
All the above implementations require stack space proportional to the height of the tree which is a call stack for the recursive and a parent (ancestor) stack for the iterative ones. In a poorly balanced tree, this can be considerable. With the iterative implementations we can remove the stack requirement by maintaining parent pointers in each node, or by threading the tree (next section).
Advantages:
Disadvantages:
Morris traversal is an implementation of in-order traversal that uses threading:
'''procedure''' levelorder(node)
queue ← '''empty queue'''
queue.enqueue(node)
'''while''' '''not''' queue.isEmpty()
node ← queue.dequeue()
visit(node)
'''if''' node.left ≠ '''null'''
queue.enqueue(node.left)
'''if''' node.right ≠ '''null'''
queue.enqueue(node.right)
If the tree is represented by an array (first index is 0), it is sufficient iterating through all elements:
'''procedure''' levelorder(array)
'''for''' i '''from''' 0 '''to''' array.size
visit(array[i])
A basic requirement for traversal is to visit every node eventually. For infinite trees, simple algorithms often fail this. For example, given a binary tree of infinite depth, a depth-first search will go down one side (by convention the left side) of the tree, never visiting the rest, and indeed an in-order or post-order traversal will never visit any nodes, as it has not reached a leaf (and in fact never will). By contrast, a breadth-first (level-order) traversal will traverse a binary tree of infinite depth without problem, and indeed will traverse any tree with bounded branching factor.
On the other hand, given a tree of depth 2, where the root has infinitely many children, and each of these children has two children, a depth-first search will visit all nodes, as once it exhausts the grandchildren (children of children of one node), it will move on to the next (assuming it is not post-order, in which case it never reaches the root). By contrast, a breadth-first search will never reach the grandchildren, as it seeks to exhaust the children first.
A more sophisticated analysis of running time can be given via infinite ; for example, the breadth-first search of the depth 2 tree above will take ω·2 steps: ω for the first level, and then another ω for the second level.
Thus, simple depth-first or breadth-first searches do not traverse every infinite tree, and are not efficient on very large trees. However, hybrid methods can traverse any (countably) infinite tree, essentially via a diagonal argument ("diagonal"—a combination of vertical and horizontal—corresponds to a combination of depth and breadth).
Concretely, given the infinitely branching tree of infinite depth, label the root (), the children of the root (1), (2), ..., the grandchildren (1, 1), (1, 2), ..., (2, 1), (2, 2), ..., and so on. The nodes are thus in a bijection correspondence with finite (possibly empty) sequences of positive numbers, which are countable and can be placed in order first by sum of entries, and then by lexicographic order within a given sum (only finitely many sequences sum to a given value, so all entries are reached—formally there are a finite number of compositions of a given natural number, specifically 2 n−1 compositions of ), which gives a traversal. Explicitly:
etc.
This can be interpreted as mapping the infinite depth binary tree onto this tree and then applying breadth-first search: replace the "down" edges connecting a parent node to its second and later children with "right" edges from the first child to the second child, from the second child to the third child, etc. Thus at each step one can either go down (append a (, 1) to the end) or go right (add one to the last number) (except the root, which is extra and can only go down), which shows the correspondence between the infinite binary tree and the above numbering; the sum of the entries (minus one) corresponds to the distance from the root, which agrees with the 2 n−1 nodes at depth in the infinite binary tree (2 corresponds to binary).
|
|
